#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <vector>
#include <queue>
#include <functional>
#include <unistd.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <utility>

/*
    前序遍历: 56 49 25 23 0 5 12 41 42 97 96 
    nonrec preorder: 56 49 25 23 0 5 12 41 42 97 96
    中序遍历: 0 5 12 23 25 41 42 49 56 96 97
    nonrec inorder: 0 5 12 23 25 41 42 49 56 96 97
    后序遍历: 12 5 0 23 42 41 25 49 96 97 56
    nonrec postorder: 12 5 0 23 42 41 25 49 96 97 56
    层序遍历: 56 49 97 25 96 23 41 0 42 5 12
    levelorder: 56 49 97 25 96 23 41 0 42 5 12
    height: 7
    node num: 11
    23 25
*/

using namespace std;

template <typename T,typename Compare = less<T>>
class NonRecBst
{
private:
    /* data */
    struct Node
    {
        T data;
        Node *left;
        Node *right;
        Node(T data):data(data),left(NULL),right(NULL){}
    };
    Node *root_;
    Compare cmp_;
    void preorder(Node *root);
    void inorder(Node *root);
    void postorder(Node *root);
    void levelorder(Node *root,int level);
    int bst_height(Node *root);
    int bst_node_num(Node *root);
    Node * rec_insert(Node *root,const T& data);
    Node * rec_query(Node *root,const T& data);
    Node * rec_remove(Node *root,const T& data);
    void findvecval(Node *node,vector<T> &vec,int start,int end);
    bool isbst(Node *root, Node *&pre);
    Node * lca(Node *node, int val1, int val2)
    {
        if (node == nullptr)
            return nullptr;

        if (cmp_(node->data, val1) && cmp_(node->data, val2))
            return lca(node->right, val1, val2);

        else if (cmp_(val1, node->data) && cmp_(val2, node->data))
            return lca(node->left, val1, val2);

        else
            return node;
    }

    // 二叉树镜像翻转
    void mirror(Node *node)
    {
        if (node == NULL)
            return;
        Node *tmp = node->left;
        node->left = node->right;
        node->right = tmp;

        mirror(node->left);
        mirror(node->right);
    }

    // 二叉树镜像对称
    bool mirror_symmetry(Node *node1, Node *node2)
    {
        if (node1 == NULL && node2 == NULL)
            return true;
        if (node1 == NULL || node2 == NULL)
            return false;
        if (node1->data != node2->data)
            return false;
        return mirror_symmetry(node1->left, node2->right) && mirror_symmetry(node1->right, node2->left);
    }

    Node *create_bst(int pre[], int i, int j, int in[], int m, int n)
    {
        if (i > j || m > n)
            return NULL;
        Node *node = new Node(pre[i]);
        int k;
        for (k = m; k <= n; k++)
        {
            if (in[k] == pre[i])
                break;
        }
        node->left = create_bst(pre, i + 1, i + k - m, in, m, k - 1);
        node->right = create_bst(pre, i + k - m + 1, j, in, k + 1, n);
        return node;
    }

public:
    NonRecBst();
    ~NonRecBst();

    void nonrec_insert(const T& data);
    void nonrec_remove(const T& data);
    bool nonrec_query(const T& data);

    // 递归前序遍历
    void preorder();

    // 递归中序遍历
    void inorder();

    // 递归后序遍历
    void postorder();

    // 递归层序遍历
    void levelorder();

    // 非递归前序遍历
    void nonrec_preorder();

    // 非递归中序遍历
    void nonrec_inorder();

    // 非递归后序遍历
    void nonrec_postorder();

    // 非递归层序遍历
    void nonrec_levelorder();

    // 计算二叉树层数
    int bst_height();
    // 计算二叉树节点个数
    int bst_node_num();

    // 递归插入
    void rec_insert(const T& data);
    // 递归查询
    bool rec_query(const T& data);
    // 递归删除
    void rec_remove(const T& data);

    // 区间查找
    void findvecval(vector<T> &vec,int start,int end);

    // 判断是否为二叉搜索树
    bool isbst();

    // 求 LCA 最近公共祖先节点
    int lca(int val1,int val2)
    {
        Node *node = lca(root_,val1,val2);
        if (node == nullptr)
        {
            throw "no lca";
        }
        return node->data;
    }

    // 二叉树镜像翻转
    void mirror()
    {
        if (!root_)
            return;

        mirror(root_);
    }

    // 二叉树镜像对称
    bool mirror_symmetry()
    {
        if (!root_)
            return true;
        return mirror_symmetry(root_->left,root_->right);
    }

    // 用前序和中序遍历构造二叉树
    void create_bst(int pre[],int in[],int len)
    {
        if (len <= 0)
            return;
        root_ = create_bst(pre,0, len-1,in,0, len-1);
    }
};

template <typename T,typename Compare>
NonRecBst<T,Compare>::NonRecBst()
        :root_(NULL)
{
}

template <typename T,typename Compare>
NonRecBst<T,Compare>::~NonRecBst()
{
    // 采用层序遍历的方法对二叉树进行销毁
    if (!root_)
        return;
    queue<Node*> q;
    q.push(root_);
    while(!q.empty())
    {
        Node * cur = q.front();
        q.pop();
        if (cur->left != NULL)
            q.push(cur->left);
        if (cur->right != NULL)
            q.push(cur->right);
        delete cur;
    }
    return;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::nonrec_insert(const T& data)
{
    // 如果二叉树为空，直接插入
    if (!root_)
    {
        root_ = new Node(data);
        cout << "insert root val = " << data << endl;
        return;
    }
    
    Node * cur = root_;
    Node * parent = NULL;
    while(cur!=NULL)
    {
        // 插入节点值等于当前节点值，直接返回
        if (data == cur->data)
            return;
        // 插入节点值小于当前节点值，往左子树遍历
        else if(cmp_(data,cur->data))
        {
            // 记录父节点
            parent = cur;
            // 继续遍历
            cur = cur->left;
        }
        // 插入节点值大于当前节点值，往右子树遍历
        else
        {
            // 记录父节点
            parent = cur;
            // 继续遍历
            cur = cur->right;
        }
    }

    // 插入节点，不是直接插入cur，而是插入到父节点的左子树或右子树
    if (cmp_(data, parent->data))
    {
        cout << "insert left val = " << data << endl;
        parent->left = new Node(data);
    }
        
    else
    {
        cout << "insert right val = " << data << endl;
        parent->right = new Node(data);
    }
}

// 从二叉树中删除节点，总共有三种情况（特殊情况，删除根节点或者bst为空单独讨论）
// 1、删除叶子节点--------可以直接删除
// 2、删除只有一个子节点的节点--------将子节点替换到删除节点的位置
// 3、删除有两个子节点的节点----------此时需要找到右子树的最小节点，或者左子树的最大节点，替换到删除节点的位置
template <typename T,typename Compare>
void NonRecBst<T,Compare>::nonrec_remove(const T& data)
{
    // 如果二叉树为空，直接返回
    if (!root_)
        return;

    Node * cur = root_;
    Node * parent = NULL;

    // 先找到节点位置，再根据情况删除
    // 退出情况有两种，一种是找到节点，另一种是遍历到空节点
    while(cur!=NULL)
    {
        // 删除节点值等于当前节点值，直接退出循环,记录父节点和当前节点位置即可
        if (data == cur->data)
        {
            cout << "found val = " << data << endl;
            break;
        }

        // 删除节点值小于当前节点值，往左子树遍历
        else if(cmp_(data,cur->data))
        {
            // 记录父节点
            parent = cur;
            // 继续遍历
            cur = cur->left;
        }
        // 删除节点值大于当前节点值，往右子树遍历
        else
        {
            // 记录父节点
            parent = cur;
            // 继续遍历
            cur = cur->right;
        }
    }

    // 如果当前节点为空，说明没有找到节点，直接返回
    if (cur == NULL)
    {
        cout << "not found val = " << data << endl;
        return ;
    }

    // 如果找到了节点，根据情况删除节点
    // 先处理情况3
    // 如果当前节点有两个子节点，找到右子树的最小节点，或者左子树的最大节点，替换到当前节点的位置
    if (cur->left != nullptr && cur->right != nullptr )
    {
        cout << "consider 3 data =" << cur->data << endl;
        parent = cur;
        // 找左子树的最大节点
        Node * pre = cur->left;
        // 左子树最大值在右侧
        while (pre->right != nullptr)
        {
            parent = pre;
            pre = pre->right;
        }
        // 替换当前节点的值
        cur->data = pre->data;
        // 让 cur 指向 pre，转换成情况1、2
        cur = pre;  
    }
    
    // cur 指向删除节点, parent 指向其父节点。统一处理情况1、2
    // cur 此时不可能拥有两个子节点，因为在上面的情况下已把情况3处理完成
    Node * child = cur->left != NULL ? cur->left : cur->right;

    // 特殊情况如果删除的是根节点
    if (cur == root_)
    {
        root_ = child;
    }

    else
    {
        cout <<  "parent = " << parent->data << endl;
        // 查看cur是parent的左子节点还是右子节点，然后把待删除节点的孩子写入其父节点的对应位置
        if (parent->left == cur)
            parent->left = child;
        else
            parent->right = child;
    }

    // 删除当前节点
    delete cur;


#if 0
    // 1、如果当前节点没有子节点，直接删除
    if (cur->left == NULL && cur->right == NULL)
    {
        // 如果当前节点是根节点，直接删除
        if (cur == root_)
        {
            delete cur;
            root_ = NULL;
        }
        // 如果当前节点不是根节点，删除当前节点
        else
        {
            if (parent->left == cur)
                parent->left = NULL;
            else
                parent->right = NULL;
            delete cur;
        }
    }

    // 2、如果当前节点只有一个子节点，将子节点替换到当前节点的位置
    else if (cur->left == NULL || cur->right == NULL)
    {
        // 如果当前节点是根节点，直接删除
        if (cur == root_)
        {
            if (cur->left != NULL)
                root_ = cur->left;
            else
                root_ = cur->right;
            delete cur;
        }
        // 如果当前节点不是根节点，删除当前节点
        else
        {
            if (parent->left == cur)
            {
                if (cur->left != NULL)
                    parent->left = cur->left;
                else
                    parent->left = cur->right;
            }
            else
            {
                if (cur->left != NULL)
                    parent->right = cur->left;
                else
                    parent->right = cur->right;
            }
            delete cur;
        }
    }

    // 3、如果当前节点有两个子节点，找到右子树的最小节点，或者左子树的最大节点，替换到当前节点的位置
    else
    {
        // 找到右子树的最小节点
        Node * min_node = cur->right;
        Node * min_parent = cur;
        while(min_node->left != NULL)
        {
            min_parent = min_node;
            min_node = min_node->left;
        }
        // 替换当前节点的值为最小节点的值
        cur->data = min_node->data;
        
        // 删除最小节点
        if (min_parent->left == min_node)
            min_parent->left = min_node->right;
        else
            min_parent->right = min_node->right;
            
        delete min_node;
    }
#endif
}


template <typename T,typename Compare>
bool NonRecBst<T,Compare>::nonrec_query(const T& data)
{
    Node * cur = root_;
    // 查找二叉树是否有对应的值
    while(cur!=nullptr)
    {
        // 找到返回true
        if (data == cur->data)
            return true;
        else if(cmp_(data,cur->data))
            cur = cur->left;
        else
            cur = cur->right;
    }

    return false;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::preorder()
{
    cout << "前序遍历: ";
    preorder(root_);
    cout << endl;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::preorder(Node * root)
{
    if (root == nullptr)
        return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::inorder()
{
    cout << "中序遍历: ";
    inorder(root_);
    cout << endl;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::inorder(Node * root)
{
    if (root == nullptr)
        return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::postorder()
{
    cout << "后序遍历: ";
    postorder(root_);
    cout << endl;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::postorder(Node * root)
{
    if (root == nullptr)
        return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::levelorder()
{
    cout << "层序遍历: ";
    int level = bst_height();
    for (size_t i = 0; i < level; i++)
    {
        levelorder(root_,i);
    }
    cout << endl;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::levelorder(Node * root, int level)
{
    if (root == nullptr)
        return;
    if (level == 0)
        cout << root->data << " ";
    else
    {
        levelorder(root->left,level-1);
        levelorder(root->right,level-1);
    }
}   

template <typename T,typename Compare>
int NonRecBst<T,Compare>::bst_height()
{
    return bst_height(root_);
}

template <typename T,typename Compare>
int NonRecBst<T,Compare>::bst_height(Node * root)
{
    if (root == nullptr)
        return 0;
    int left = bst_height(root->left);
    int right = bst_height(root->right);
    return left > right ? left + 1 : right + 1;
}

template <typename T,typename Compare>
int NonRecBst<T,Compare>::bst_node_num()
{
    return bst_node_num(root_);
}

template <typename T,typename Compare>
int NonRecBst<T,Compare>::bst_node_num(Node * root)
{
    if (root == nullptr)
        return 0;
    return bst_node_num(root->left) + bst_node_num(root->right) + 1;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::rec_insert(const T& data)
{
    root_ = rec_insert(root_,data);    
}

template <typename T,typename Compare>
typename NonRecBst<T, Compare>::Node* 
NonRecBst<T, Compare>::rec_insert(Node* node, const T& data)
{
    if (node == nullptr)
    {
        node = new Node(data);
        return node;
    }
    if (data == node->data)
        return nullptr;
    else if (cmp_(data,node->data))
        node->left = rec_insert(node->left,data);
    else
        node->right = rec_insert(node->right,data);
    return node;
}

template <typename T,typename Compare>
bool NonRecBst<T,Compare>::rec_query(const T& data)
{
    return nullptr != rec_query(root_,data);
}

template <typename T,typename Compare>
typename NonRecBst<T,Compare>::Node *
NonRecBst<T,Compare>::rec_query(Node* node, const T& data)
{
    if (node == nullptr)
        return nullptr;
    if (data == node->data)
        return node;
    else if (comp_(data,node->data))
        return rec_query(node->left,data);
    else
        return rec_query(node->right,data);
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::rec_remove(const T& data)
{
    root_ = rec_remove(root_,data);
}

template <typename T,typename Compare>
typename NonRecBst<T,Compare>::Node* 
NonRecBst<T,Compare>::rec_remove(Node* node, const T& data)
{
    if (node == nullptr)
        return nullptr;
    if (data == node->data)
    {
        // 三种情况
        // 1. 叶子节点
        // 2. 只有一个子节点
        // 3. 有两个子节点
        // 先处理情况3
        if (node->left != nullptr && node->right != nullptr)
        {
            // 寻找待删除节点的前驱或者后继节点
            // 找前驱，向其左子节点的右子树寻找
            Node* pre = node->left;
            while (pre->right != nullptr)
                pre = pre->right;
            // 将前驱节点的值赋给待删除节点，跳出后，再处理
            node->data = pre->data;
            // 通过递归直接删除前驱节点
            node->left = rec_remove(node->left,pre->data);
        }

        // 处理情况2
        else if (node->left == nullptr)
        {
            Node* tmp = node->right;
            delete node;
            return tmp;
        }
        else if (node->right == nullptr)
        {
            Node* tmp = node->left;
            delete node;
            return tmp;
        }

        // 处理情况1
        else
        {
            // 直接删除叶子节点
            delete node;
            return nullptr;
        }
    }

    else if (cmp_(data,node->data))
        node->left = rec_remove(node->left,data);
    else
        node->right = rec_remove(node->right,data);

    return node;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::nonrec_preorder()
{
    cout << "nonrec preorder: ";
    if (root_ == nullptr)
    {
        return ;
    }
    
    stack<Node*> s;
    s.push(root_);
    while (!s.empty())
    {
        Node* node = s.top();
        cout << node->data << " ";
        s.pop();
        if (node->right != nullptr)
            s.push(node->right);
        if (node->left != nullptr)
            s.push(node->left);
    }
    cout << endl;
    return ;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::nonrec_inorder()
{
    cout << "nonrec inorder: ";
    if (root_ == nullptr)
    {
        return ;
    }
    
    stack<Node*> s;
    Node* node = root_;
    while (!s.empty() || node != nullptr)
    {
        if (node != nullptr)
        {
            s.push(node);
            node = node->left;
        }
        else
        {
            node = s.top();
            cout << node->data << " ";
            s.pop();
            node = node->right;
        }
    }
    cout << endl;
    return ;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::nonrec_postorder()
{
    cout << "nonrec postorder: ";
    if (root_ == nullptr)
    {
        return ;
    }
    // 后序遍历还可以使用双栈来实现
    stack<Node*> s;
    Node* node = root_;
    Node* pre = nullptr;
    while (!s.empty() || node != nullptr)
    {
        if (node != nullptr)
        {
            s.push(node);
            node = node->left;
        }
        else
        {
            node = s.top();
            // 如果当前节点的右子树为空，或者右子树已经访问过，那么访问当前节点
            if (node->right == nullptr || node->right == pre)
            {
                cout << node->data << " ";
                s.pop();
                pre = node;
                node = nullptr;
            }
            // 否则，访问右子树
            else
            {
                node = node->right;
            }
        }
    }
    cout << endl;
    return ;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::nonrec_levelorder()
{
    cout << "levelorder: ";
    if (root_ == nullptr)
    {
        return ;
    }
    // 层序遍历，及广度优先算法，非递归采用队列来实现按
    // 先将根节点入队，然后出队，访问，再将其左右子节点入队，再出队，访问，以此类推
    // 即每次取得都是对头元素
    queue<Node*> q;
    q.push(root_);
    while (!q.empty())
    {
        Node* node = q.front();
        cout << node->data << " ";
        q.pop();
        if (node->left != nullptr)
            q.push(node->left);
        if (node->right != nullptr)
            q.push(node->right);
    }
    cout << endl;
    return ;
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::findvecval(vector<T>& vec, int start, int end)
{
    findvecval(root_, vec, start, end);
}

template <typename T,typename Compare>
void NonRecBst<T,Compare>::findvecval(Node* node, vector<T>& vec, int start, int end)
{
    if (node == nullptr)
        return ;
    
    // 需要采用中序遍历，因为中序遍历是从小到大，所以先访问的节点是较小的节点

    if (node->left != nullptr && node->left->data >= start)
        findvecval(node->left, vec, start, end);
    if (node->data >= start && node->data <= end)
        vec.push_back(node->data);
    if (node->right != nullptr && node->right->data <= end)
        findvecval(node->right, vec, start, end);
}

template <typename T,typename Compare>
bool NonRecBst<T,Compare>::isbst()
{
    Node* pre = nullptr;
    return isbst(root_, pre);
}

template <typename T,typename Compare>
bool NonRecBst<T,Compare>::isbst(Node* node, Node*& pre)
{
    // 如果仅仅采用比较前后节点的方法，则只是比较局部，无法保证全局有序，如右侧孙子节点比自身节点小

    // 空树是BST
    if (node == nullptr)
        return true;

    // 1. 递归检查左子树
    if (!isbst(node->left, pre))
        return false;
    // 2. 检查当前节点是否大于前驱
    if (pre != nullptr && pre->data >= node->data)
        return false;
    // 3. 更新前驱为当前节点
    pre = node;
    // 4. 递归检查右子树
    return isbst(node->right, pre);
}

// 测试 LCA 最近公共祖先节点问题
void test_lca()
{
    NonRecBst<int> bst;
    int arr[] = {58,49,25,56,97,41,42,23,0,5,96};
    for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
    {
        // bst.nonrec_insert(arr[i]);
        bst.rec_insert(arr[i]);
    }
    // bst.nonrec_insert(12);
    bst.rec_insert(12);
    bst.rec_remove(58);

    cout << "LCA 41 42: " << bst.lca(23, 41)<< endl;
}

// 测试使用前序和中序构造二叉树
void test_construct()
{
    NonRecBst<int> bst;
    int pre[] = {56, 49, 25, 23, 0, 5, 12, 41, 42, 97, 96};
    int in[] = {0, 5, 12, 23, 25, 41, 42, 49, 56, 96, 97};
    bst.create_bst(pre, in, sizeof(pre)/sizeof(pre[0]));
    bst.preorder();
    bst.inorder();
}


int main(int argc, char *argv[])
{
    NonRecBst<int> bst;
    int arr[] = {58,49,25,56,97,41,42,23,0,5,96};
    for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
    {
        // bst.nonrec_insert(arr[i]);
        bst.rec_insert(arr[i]);
    }
    // bst.nonrec_insert(12);
    bst.rec_insert(12);
    bst.rec_remove(58);
    // cout << "query 12: " << bst.nonrec_query(12) << endl;
    // cout << "query 58: " << bst.nonrec_query(58) << endl;

    // bst.nonrec_remove(58);
    // bst.nonrec_remove(12);
    // // bst.nonrec_remove(560);

    // cout << "query 12: " << bst.nonrec_query(12) << endl;
    // cout << "query 58: " << bst.nonrec_query(58) << endl;

    bst.preorder();
    bst.nonrec_preorder();
    bst.inorder();
    bst.nonrec_inorder();
    bst.postorder();
    bst.nonrec_postorder();
    bst.levelorder();
    bst.nonrec_levelorder();

    cout << "height: " << bst.bst_height() << endl;
    cout << "node num: " << bst.bst_node_num() << endl;

    vector<int> vec;
    bst.findvecval(vec, 20, 30);

    for (auto i : vec)
        cout << i << " ";

    cout << endl;

    cout << "当前二叉树是否是二叉搜索树： " << bst.isbst() << endl;

    test_lca();

    test_construct();

    return 0;
}
